package com.ainge.easystudy.binary.tree;

import java.io.Serializable;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 利用递归实现简单二叉搜索树
 *
 * @author: Ainge
 * @Time: 2021/9/14 21:07
 */
public class SimpleBinaryTree {


    public static void main(String[] args) {
        LinkedList<Integer> data = new LinkedList<>(Arrays.asList(3, 2, 9, null, null, 10, null, null, 8, null, 4));
        TreeNode treeNode = SimpleBinaryTree.createTreeNode(data);
        System.out.println("=====前序遍历====");
        preOrderTraverse(treeNode);
        System.out.println("=====前序遍历====");
        preOrderTraverseByStack(treeNode);
        System.out.println("=====中序遍历====");
        inOrderTraverse(treeNode);
        System.out.println("=====后序遍历====");
        postOrderTraverse(treeNode);
        System.out.println("=====广度优先遍历====");
        levelOrderTraverse(treeNode);
    }

    /**
     * 简单创建一个二叉搜索树
     *
     * @param inputData
     * @return
     */
    public static TreeNode createTreeNode(LinkedList<Integer> inputData) {
        Integer data;
        if (inputData == null || inputData.isEmpty() ||
                (data = inputData.removeFirst()) == null) {
            return null;
        }
        TreeNode node = new TreeNode(data);
        node.leftChild = createTreeNode(inputData);
        node.rightChild = createTreeNode(inputData);
        return node;
    }

    // 前序遍历
    public static void preOrderTraverse(TreeNode node) {
        if (node == null) return;
        System.out.println(node.data);
        preOrderTraverse(node.leftChild);
        preOrderTraverse(node.rightChild);
    }
    public static void preOrderTraverseByStack(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.empty()){
            while (node != null){
                System.out.println(node.data);
                stack.push(node);
                node = node.leftChild;
            }
            if(!stack.empty()){
                node = stack.pop();
                node = node.rightChild;
            }
        }
    }

    // 中序遍历
    public static void inOrderTraverse(TreeNode node) {
        if (node == null) return;
        inOrderTraverse(node.leftChild);
        System.out.println(node.data);
        inOrderTraverse(node.rightChild);
    }

    // 后序遍历
    public static void postOrderTraverse(TreeNode node) {
        if (node == null) return;
        postOrderTraverse(node.leftChild);
        postOrderTraverse(node.rightChild);
        System.out.println(node.data);
    }

    public static void levelOrderTraverse(TreeNode root){
        if(root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode treeNode = queue.poll();
            System.out.println(treeNode.data);
            if(treeNode.leftChild != null){
                queue.offer(treeNode.leftChild);
            }
            if(treeNode.rightChild != null){
                queue.offer(treeNode.rightChild);
            }
        }
    }


    private static class TreeNode implements Serializable {
        /**
         * 存储数据
         */
        int data;
        /**
         * 左孩子
         */
        TreeNode leftChild;
        /**
         * 右孩子
         */
        TreeNode rightChild;

        TreeNode(int data) {
            this.data = data;
        }
    }
}
